package sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{11, 23, 37, 5, 21, 17, 23, 31, 40, 2};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int low, int high) {
        int index = low;
        int temp = arr[index];
        if(low < high) {
            // 获取基准元素最终位置
            index = getIndex(arr, low, high, temp);
            arr[index] = temp;

            // 递归排序
            quickSort(arr, low, index - 1);
            quickSort(arr, index + 1, high);
        }
    }

    private static int getIndex(int[] arr, int low, int high, int benchmark) {
        while (low < high) {
            // 先从尾指针开始移动
            while (low < high && arr[high] >= benchmark) {
                high--;
            }

            arr[low] = arr[high];

            // 头指针开始移动
            while (low < high && arr[low] <= benchmark) {
                low++;
            }

            arr[high] = arr[low];
        }
        return low;
    }
}
